/**
 * 最大子段和，经典问题
 * 
 */
using vi = vector<int>;
class Solution {

int N;
vi D;
vi U;

public:
    int maxSubArray(vector<int>& nums) {
        N = nums.size();
        D.assign(N, 0);
        U.assign(N, 0);
        D[0] = U[0] = nums[0];
        for(int i=1;i<N;++i){
            U[i] = max(U[i - 1] + nums[i], nums[i]);
            D[i] = max(D[i - 1], U[i]);
        }
        return D[N - 1];
    }

};